import java.math.BigDecimal;
import java.util.*;


class Node{
    int n;
    Node next;
    public Node(int n){
        this.n = n;
    }

}

public class Demo12 {


/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();

            int count = 0;
            for(int i = 2;i*i<=n;i++){
                int sum = 0;
                for(int j = 2;j*j<=i;j++){
                    if(i%j==0){
                        if (i/j==j){
                            sum+=j;
                        }else{
                            sum=sum+j+i/j;
                        }
                    }
                }
                if (sum+1==i){
                    count++;
                }
            }
            System.out.println(count);

        }
    }*/





/*

    public int findMinimum(int n, int[] left, int[] right) {
        int sum = 0;
        int leftSum = 0;
        int rigthSum = 0;
        int leftMin = Integer.MAX_VALUE;
        int rightMin = Integer.MIN_VALUE;
        for(int i =0;i<n;i++){
            if (left[i] == 0){
                sum+=right[i];
            }else if(right[i]==0){
                sum+=left[i];
            }
            if (left[i]!=0 && right[i]!=0){
                leftMin = Math.min(leftMin,left[i]);
                rightMin = Math.min(rightMin,right[i]);
                leftSum+=left[i];
                rigthSum+=right[i];
            }
        }
        sum+=Math.min(leftSum-leftMin,rigthSum-rightMin)+1;
        return sum;
    }
*/


/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int count = 0;
            while (a!=0){
                if ((a&1)==1){
                    count++;
                }
                a>>=1;
            }
            System.out.println(count);
        }
    }*/


/*
    public static int sum = 0;
    public static int mult = 1;
    public static int count = 0;
    public static int[] nums;
    public static Set<List<Integer>> set;
    public static List<Integer> path;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            nums = new int[n];
            path = new ArrayList<>();
            set = new HashSet<>();

            for(int i = 0;i<n;i++){
                nums[i] = in.nextInt();
            }

            Arrays.sort(nums);

            dfs(nums,n,0);

            System.out.println(count);



        }
    }

    private static void dfs(int[] nums, int n, int pos) {

        for(int i =pos ;i<n;i++){
            sum+=nums[i];
            mult*=nums[i];

            if (sum>mult){
                count++;
                dfs(nums,n,i+1);
            }else if(nums[i]==1){
                dfs(nums,n,i+1);
            }else{
                break;
            }

            sum-=nums[i];
            mult/=nums[i];
            while (i<n-1&&nums[i]==nums[i+1]){
                i++;
            }
        }

    }*/


//    private static void dfs(int[] nums, int n, int pos) {
//        sum+=nums[pos];
//        mult*=nums[pos];
//        path.add(nums[pos]);
//
//        if (sum>mult){
//            set.add(new ArrayList<>(path));
//        }
//
//        for(int i =pos;i<n-1;i++){
//                dfs(nums,n,i+1);
//                sum-=nums[i+1];
//                mult/=nums[i+1];
//                path.remove(path.size()-1);
//                if (sum<=mult && nums[i] != 1){
//                    break;
//                }
//                while(i<n-1 && nums[i] == nums[i+1]){
//                    i++;
//                }
//        }
//
//    }











   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
           int n = in.nextInt();
           int[] a = new int[n];
           for(int i = 0;i<n;i++){
               a[i] = in.nextInt();
           }

           Arrays.sort(a);

           int count = dfs(a,n,0,0,1);
            System.out.println(count);




        }
    }

    private static int dfs(int[] a,int n,int pos,int sum,int multi) {

        int count = 0;
        for(int i=pos;i<n;i++){
            sum+=a[i];
            multi*=a[i];
            if (sum>multi){
                count = count+1+dfs(a,n,i+1,sum,multi);
            }else if(a[i]==1){
                count=count+dfs(a,n,i+1,sum,multi);
            }else{
                break;
            }
            sum-=a[i];
            multi/=a[i];
            while (i<n-1 && a[i]==a[i+1]){
                i++;
            }
        }
        return count;
    }
*/




   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int year = in.nextInt();
            int month = in.nextInt();
            int day = in.nextInt();

            int sum = 0;
            int[] arr = {0,31,28,31,30,31,30,31,31,30,31,30,31};

            if ((year%4 == 0&&year%100!=0) || (year%400==0)){
                arr[2] = 29;
            }
            for(int i =1;i<month;i++){
                sum+=arr[i];
            }
            System.out.println(sum+day);



        }
    }
*/









/*
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();

        int[] step = new int[m+1];
        for(int i=0;i<m+1;i++){
            step[i] = Integer.MAX_VALUE;
        }

        step[n] = 0;
        for(int i = n;i<m;i++){
            if (step[i] == Integer.MAX_VALUE){
                continue;
            }
            List<Integer> list = dic(i);
            for(int j :list){
                if (i+j<=m && step[i+j]!=Integer.MAX_VALUE){
                    step[i+j] = Math.min(step[i+j],step[i]+1);
                }else if(i+j<=m){
                    step[i+j] = step[i]+1;
                }
            }
        }
        if (step[m]==Integer.MAX_VALUE){
            System.out.println(-1);
        }else{
            System.out.println(step[m]);
        }
    }

    public static List<Integer> dic(int num){
        List<Integer> list = new ArrayList<>();
        for(int i = 2;i*i<=num;i++){
            if (num%i==0){
                list.add(i);
                if (num/i!=i){
                    list.add(num/i);
                }
            }
        }
        return list;

    }*/


/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            int count = 0;
            for(int i = 0;i<str.length();i++){
                //遇到双引号时要一直遍历，知道碰到第二个双引号
                if (str.charAt(i) == '"'){
                    do{
                        i++;
                    }while(str.charAt(i)!='"');
                }
                if (str.charAt(i)==' '){
                    count++;
                }

            }

            System.out.println(count+1);
            int flag = 1;
            for(int i = 0;i<str.length();i++){
                if (str.charAt(i) =='"'){
                    flag^=1;
                }
                if (str.charAt(i)!=' ' && str.charAt(i)!='"'){
                    System.out.print(str.charAt(i));
                }

                if (flag==0 && str.charAt(i) == ' '){
                    System.out.print(str.charAt(i));
                }
                if (flag==1 && str.charAt(i) == ' '){
                    System.out.println();
                }


            }


        }
    }*/


   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int harf = n/2;
            for(int i = harf;i>0;i--){
                if (isPrime(i) && isPrime(n-i)){
                    System.out.println(i);
                    System.out.println(n-i);
                    break;
                }
            }

        }
    }
    public static boolean isPrime(int m ){
        for(int i = 2;i*i<=m;i++){
            if (m%i==0){
                return false;
            }
        }
        return true;
    }
*/


/*    public int binInsert(int n, int m, int j, int i) {
        m<<=j;
        return m|n;

    }*/






/*    public int getLCA(int a, int b) {
       while (a!=b){
           if (a>b){
               a/=2;
           }else{
               b/=2;
           }
       }
       return a;


    }*/






/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int count = 0;
            int max = 0;
            while (a!=0){
                if ((a&1)==1){
                    count++;
                    max = Math.max(max, count);
                }else{
                    count=0;
                }
                a=a>>1;
            }
            System.out.println(max);
        }
    }*/










    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
           int n = in.nextInt();
           Set<Integer> hash = new HashSet<>();
           if (n==2){
               System.out.println(1);
           }else{
               for(int i = 2;i<=n/2;i++){
                   if (n%i==0){
                       int ret = i;
                       boolean exist = false;
                       for(int j = 2;j<ret;j++){
                           if (i%j==0 && hash.contains(j)){
                               exist = true;
                               break;
                           }
                       }
                       if (!exist) {
                           hash.add(i);
                       }
                   }
               }
               System.out.println(hash.size());
           }

//            for(int i =0;i<hash.size();i++ ){
//                System.out.print(hash.toArray()[i]+" ");
//            }


        }
    }
*/








/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            char[] arr = str.toCharArray();
            String ret = "";
            for(int i = 0;i<arr.length; i++){
                if (arr[i]>='A' && arr[i]<'F'){
                    ret += (char)('V'+arr[i]-'A');
                }else if(arr[i]==' '){
                    ret+=' ';
                } else{
                    ret += (char)(arr[i]-5);
                }
            }
            System.out.println(ret);


        }
    }*/





/*
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
           int n = in.nextInt();
           if (n == 0){
               break;
           }
           if(n<=3){
               System.out.println(1);
           }else{
               int count = 0;
               while (n>0){
                   n/=3;
                   count++;
               }
               System.out.println(count);
           }





        }
    }
*/






  /*  public static void main(String[] args) {
        System.out.println(getFirstUnFormedNum(new int[]{3,2,5}));
    }


    public static int getFirstUnFormedNum(int[] arr) {
        int max = 0;
        int min = Integer.MAX_VALUE;
        int n = arr.length;
        for(int i = 0;i<n;i++){
            max += arr[i];
            min = Math.min(arr[i], min);
        }

        //将子数组的值存到set里面
        HashSet<Integer> set = new HashSet<>();

        int num = 1<<n;
        for(int i = 0;i<num;i++){
            int ret = i;
            int k = 0;
            int sum = 0;
            while (ret>0) {
                if ((ret & 1) == 1) {
                    sum += arr[k];
                }
                ret = ret >> 1;
                k++;
            }
            set.add(sum);
        }


        for(int i = min;i<=max;i++){
            if (!set.contains(i)){
                return i;
            }
        }

        return max+1;

    }
*/









    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
           int n = in.nextInt();
           int count = 0;
           int x = 1;
           if (n==0){
               break;
           }
           while (true){
               count = 0;
               int ret = x;
               boolean flag = false;
               for(int i = 0;i<n;i++){
                   if ((ret-1)%5==0){
                        ret = (ret-1)/5*4;
                        count++;
                        if (i==n-1){
                            flag = true;
                        }
                   }else{
                       break;
                   }
               }
               count+=ret;
               if (flag){
                   System.out.println(x+" " +count);
                   break;
               }
               x++;
           }




        }




    }*/


    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Node head = new Node(0);
        int n = in.nextInt();
        for(int i = 0;i<n;i++){
            Node node = new Node(in.nextInt());
            head.next = node;
            head = node;
        }

        int left = in.nextInt();
        int right = in.nextInt();

        Node cur = head;
        for(int i=0;i<left;i++){
            cur = cur.next;
        }
        Node cur1 = cur;
        for(int i = left;i<right;i++){
            cur1 = cur1.next;
        }





    }*/

   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0;i<n;i++){
            arr[i] = in.nextInt();
        }
        int left = in.nextInt();
        int right = in.nextInt();

        for(int i = right-1;i>=left-1;i++){
            System.out.print(arr[i]+" ");
        }
        for(int i = right;i<n;i++){
            System.out.print(arr[i]+" ");
        }


    }*/















   /* public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        for(int i = 0;i<n;i++){
            dp[i] = 1;
        }

        int ret = 1;
        for(int i = 1;i<n;i++){
            for(int j=0;j<i;j++){
                if (nums[j]<nums[i]){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
                ret = Math.max(ret,dp[i]);
            }
        }

        return ret;


    }*/



  /*  public int findSubstringInWraproundString(String ss) {
        int n = ss.length();
        int[] dp = new int[n];

        for(int i = 0;i<n;i++){
            dp[i]=1;
        }

        char[] s = ss.toCharArray();
        for(int i =1;i<n;i++){
            if (s[i-1]+1==s[i] || (s[i-1]=='z' && s[i]=='a')){
                dp[i] = dp[i-1]+1;
            }
        }

        int[] hash = new int[26];
        for(int i = 0;i<n;i++){
            hash[s[i]-'a'] = Math.max(hash[s[i]-'a'],dp[i]);
        }
        int sum = 0;
        for(int i =0;i<26;i++){
            sum += hash[i];
        }
        return sum;


    }
*/





    /*public boolean wordBreak(String s, List<String> wordDict) {
        //优化，将字典中的单词存到hash表中
        Set<String> hash = new HashSet<>(wordDict);

        int  n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        s = " "+s; //处理下标的映射关系

        for(int i = 1;i<=n;i++){
            for(int j = i;j>=1;j--){
                if (dp[j-1] && hash.contains(s.substring(j,i+1))){
                    dp[i] = true;
                    break;
                }
            }


        }
        return dp[n];




    }*/









/*    public int maxTurbulenceSize(int[] arr) {
        int n= arr.length;

        int[] f = new int[n];
        int[] g = new int[n];
        for(int i =0;i<n;i++){
            f[i]=1;
            g[i]=1;
        }
        int max = 1;
        for(int i =1;i<n;i++){
            if (arr[i-1]<arr[i]){
                f[i] = g[i-1]+1;
            }
            else if(arr[i-1]>arr[i]){
                g[i] = f[i-1]+1;
            }
            max = Math.max(max,Math.max(f[i],g[i]));
        }
        return max;
    }*/


/*    public int numberOfArithmeticSlices(int[] nums) {

        int n = nums.length;
        int[] dp = new int[n];
        int sum = 0;
        for(int i = 2;i<n;i++){
            if (nums[i] - nums[i-1] == nums[i-1]-nums[i-2]){
                dp[i] = dp[i-1]+1;
            }else if(nums[i] - nums[i-1] != nums[i-1]-nums[i-2]){
                dp[i] = 0;
            }
            sum += dp[i];

        }
        return sum;



    }*/







/*    public int getMaxLen(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];


        int ret = -0xffffff;
        for(int i = 1;i<=n;i++){
            if (nums[i-1] >0 ){
                f[i] = f[i-1]+1;
                g[i] = g[i-1]==0?0:g[i-1]+1;
            }
            if (nums[i-1]<0){
                f[i] = g[i-1]==0?0:g[i-1]+1;
                g[i] = f[i-1]+1;
            }

            ret = Math.max(ret,f[i]);

        }
        return ret;




    }*/





/*    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n + 1];
        f[0] = 1;
        g[0] = 1;
        int max = -0xffffff;
        for(int i = 1;i<=n;i++){
            if (nums[i-1] >0){
                f[i] = Math.max(nums[i-1],f[i-1]*nums[i-1]);
                g[i] = Math.min(nums[i-1],g[i-1]*nums[i-1]);
            }
            if (nums[i-1]<0){
                f[i] = Math.max(nums[i-1],g[i-1]*nums[i-1]);
                g[i] = Math.min(nums[i-1],f[i-1]*nums[i-1]);
            }
            max = Math.max(max, f[i]);
        }

        return max;
    }*/










/*

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case

            String a = in.next();
            String b = in.next();
            String c = in.next();

            BigDecimal a1 = new BigDecimal(a);
            BigDecimal b1 = new BigDecimal(b);
            BigDecimal c1 = new BigDecimal(c);

            List<BigDecimal> list = new ArrayList<>();
            list.add(a1);
            list.add(b1);
            list.add(c1);

            list.sort(new Comparator<BigDecimal>() {
                @Override
                public int compare(BigDecimal o1, BigDecimal o2) {
                    return o2.compareTo(o1);
                }
            });
            System.out.println(list.get(0)+":"+list.get(1)+":"+list.get(2));

            if (list.get(1).add(list.get(2)).compareTo(list.get(0))>0
             && list.get(0).subtract(list.get(1)).compareTo(list.get(2))<0 ){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }


        }
    }


*/










/*    public int Add(int num1,int num2) {

        int tmp = num1^num2;
        int c = (num1&num2)<<1;

        while (c!=0) {
            tmp = tmp^c;
            c = (tmp&c)<<1;
        }
        return tmp;


    }*/









/*    public int maxSubarraySumCircular(int[] nums) {

        int n = nums.length;
        int dp[] = new int[n+1];
        dp[0] = 0;
        int dp2[] = new int[n+1];
        dp[0] = 0;
        int ret1 = -0xffffff;
        int ret2 = 0xffffff;
        int sum = 0;
        for(int i = 1;i<=n;i++){
            sum+=nums[i-1];
            dp[i] = Math.max(dp[i-1]+nums[i-1],nums[i-1]);
            dp2[i] = Math.min(dp2[i-1]+nums[i-1],nums[i-1]);
            if (ret1<dp[i]){
                ret1 = dp[i];
            }
            if (ret2<dp2[i]){
                ret2 = dp2[i];
            }
        }
        int max = ret1>(sum-ret2)?ret1:(sum-ret2);
        return max;



    }*/



/*    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int ret = -0xffffff;
        for(int i = 0;i<n;i++){
            int tmp = 0;
            for(int j = i;j<n;j++){
                tmp+=nums[j];
                if (tmp > ret){
                    ret = tmp;
                }
            }
        }
        return ret;
    }*/


/*
    public int maxSubArray(int[] nums) {

        int n = nums.length;
        int[] dp = new int[n+1];

        int ret = 0;
        for(int i=1;i<=n;i++){
            dp[i] = Math.max(nums[i-1],dp[i-1]+nums[i-1]);
            if (dp[i]>ret){
                ret = dp[i];
            }
        }

        return  ret;

    }
*/




/*    public int maxProfit(int k, int[] prices) {



        int n = prices.length;
        k = Math.min(k,n/2);
        int[][] f = new int[n][k+1];
        int[][] g = new int[n][k+1];

        for (int i = 0;i<=k;i++){
            f[0][i] = -0x3f3f3f;
            g[0][i] = -0x3f3f3f;
        }
        f[0][0] = -prices[0];
        g[0][0] = 0;


        for(int i = 1;i<n;i++){
            for(int j = 0;j<=k;j++){
                f[i][j] = Math.max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j] = g[i-1][j];
                if (j>0) g[i][j] = Math.max(g[i][j],f[i][j-1]+prices[i]);

            }
        }

        int ret = 0;
        for(int i = 0;i<=k;i++){
            if (g[n-1][i]>ret){
                ret = g[n-1][i];
            }
        }
        return ret;
    }*/












/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()){
            String str1 = in.next();
            String str2 = in.next();
            BigDecimal a = new BigDecimal(str1);
            BigDecimal b = new BigDecimal(str2);
            BigDecimal c = new BigDecimal("6.28");
            System.out.println(b.multiply(c).compareTo(a)>0?"Yes":"No");

        }



    }*/
/*
    public int jumpFloorII (int number) {
        return (int) Math.pow(2,number-1);

    }*/







    /*public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];

        f[0][0] = -prices[0];
        f[0][1] = -0x3f3f3f;
        f[0][2] = 0x3f3f3f;
        g[0][1] = -0x3f3f3f;
        g[0][2] = 0x3f3f3f;


        for(int i = 1;i<n;i++){
            for(int j =0;j<3;j++){
                f[i][j] = Math.max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j] = g[i-1][j];
                if (j>0) g[i][j] = Math.max(g[i][j],f[i-1][j-1]+prices[i]);
            }

        }
        int ret = 0;
        for(int i = 0;i<3;i++){
            ret = Math.max(ret,g[n-1][i]);
        }
        return ret;




    }
*/




/*    public static void main(String[] args) {
        int[] arr = {3,3,5,0,0,3,1,4};
        maxProfit(arr);
    }

    public static int maxProfit(int[] prices) {
        int n = prices.length;
        if (n==1){
            return 0;
        }

        List<Integer> arr = new ArrayList<>();
        int left = 0,right = 0;

        while (right<n-1){
            while (right<n-1 && prices[right+1]<=prices[right]){
                left++;
                right++;
            }
            while (right <n-1 && prices[right+1] > prices[right] ) {
                right++;
            }
            int tmp = prices[right]-prices[left];
            arr.add(tmp);
            left = right;
        }
        arr.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        int[] array = new int[arr.size()];
        for(int i = 0;i<arr.size();i++){
            array[i] = arr.get(i);
        }
        if (array.length == 1){
            return array[0];
        }
        if (array.length >1){
            return array[0]+array[1];
        }
        return 0;


    }*/









/*    public static void main(String[] args) {
        int[] arr = {1,2,3,0,2};
        System.out.println(maxProfit(arr,));
    }
    public static int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[][] dp = new int[n][2];

        dp[0][0] = -prices[0];

        for(int i = 1;i<n;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1] = Math.max(dp[i-1][0]+prices[i]-fee,dp[i-1][1]);
        }
        return Math.max(dp[n-1][0],dp[n-1][1]);

    }*/






/*    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];

        dp[0][0] = -prices[0];

        for(int i = 1;i<n;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][2]);
            dp[i][2] = dp[i-1][0]+prices[i];
        }
        return Math.max(dp[n-1][1],dp[n-1][2]);



    }*/






   /* public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
           int n = in.nextInt();
           int[] arr = new int[n];
           for(int i = 0;i<n;i++){
               arr[i] = in.nextInt();
           }
           String str = "";
           for(int i =0;i<n;i++){
               int count = fib(arr[i]);
               String tmp = String.valueOf(count);
               if (tmp.length()>4){
                   str += tmp.substring(tmp.length()-4);
               }else if(tmp.length()==4){
                   str += tmp;
               }else{
                   for(int k =tmp.length();k<4;k++){
                       str += '0';
                   }
                   str+=tmp;
               }
           }
            System.out.println(str);


        }
    }

    private static int fib(int i) {
        int a = 1;
        int b = 2;
        if (i==1){
            return 1;
        }
        if (i==2){
            return 2;
        }
        int c = 0;
        while (i>2){
            c = a+b;
            a = b;
            b = c;
            i--;
        }
        return c;
    }*/

/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()){
            String str = in.nextLine();
            while (str!=null){
                int count = 0;
                for(int i=0;i<str.length();i++){
                    count+=str.charAt(i)-'0';
                }
                if (count<10){
                    System.out.println(count);
                    str = null;
                }else{
                    str = String.valueOf(count);
                }
            }

        }
    }*/



/*
    static int[][] dp;
    static int[][] dp1;
    static int[][] vis;
    static int count = 0;
    static int m;
    static int n;
    static  int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    static boolean flag = false;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        m = in.nextInt();
        n = in.nextInt();
        int[][] nums = new int[m][n];
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                nums[i][j] = in.nextInt();
            }
        }
        vis = new int[m][n];
        dp = new int[m*n][2];
        dp1 = new int[m*n][2];
        dfs(nums,0,0);

        for(int i = 0;i<count;i++){
            System.out.println("("+dp[i][0]+","+dp[i][1]+")");
        }





    }

    private static void dfs(int[][] nums, int x, int y) {

        if (nums[x][y]==0){
            dp[count][0] = x;
            dp[count][1] = y;
            count++;
            vis[x][y] = 1;
        }

        if (x==m-1 && y==n-1){
            for(int z = 0;z<m*n;z++){
                dp1[z] = dp[z];
            }
            flag = true;
            return;
        }

        for(int k = 0;k<4;k++){
            int x1 = x+dx[k];
            int y1 = y+dy[k];
            if (x1>=0&&x1<m&&y1>=0&&y1<n&&vis[x1][y1]==0&&nums[x1][y1]==0){
                dfs(nums,x1,y1);
                if (flag){
                    return;
                }
                count--;
                dp[count][0] = 0;
                dp[count][1] = 0;
                vis[x1][y1]=0;
            }
        }


    }
*/


/*    public int getMost(int[][] board){
        int[][] dp = new int[7][7];
        for(int i = 1;i<=6;i++){
            for(int j = 1;j<=6;j++){
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+board[i-1][j-1];
            }
        }
        return dp[6][6];

    }*/



    /*public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()){
            String str = in.nextLine();
            int sum = 0;
            int sum1 = getLen(str);
            int sum2 = getChar(str);
            int sum4 = getSym(str);
            int sum3 = getNum(str);
            if (sum2==20 && sum3>=1 && sum4>=1){
                sum = sum1+sum2+sum3+sum4+5;
            }else if(sum2 ==10 && sum3>=1 && sum4 >=1){
                sum = sum1+sum2+sum3+sum4+3;
            }else if(sum2 ==10 && sum3>=1 && sum4 == 0){
                sum = sum1+sum2+sum3+sum4+2;
            }else{
                sum = sum1+sum2+sum3+sum4;
            }
            if (sum>=90){
                System.out.println("VERY_SECURE");
            }else if(sum>=80){
                System.out.println("SECURE");
            }else if(sum>=70){
                System.out.println("VERY_STRONG");
            }else if(sum>=60){
                System.out.println("STRONG");
            }else if(sum>=50){
                System.out.println("AVERAGE");
            }else if(sum>=25){
                System.out.println("WEAK");
            }else if(sum>=0){
                System.out.println("VERY_WEAK");
            }

        }





    }

    public static int getLen(String str) {
        if (str.length() <= 4) {
            return 5;
        } else if (str.length() >= 5 && str.length() <= 7) {
            return 10;
        } else if (str.length() >= 8) {
            return 25;
        }
        return 0;
    }

    public static int getChar(String str) {
        int small = 0;
        int big = 0;
        for(int i=0;i<str.length();i++){
            if (str.charAt(i) >= 'a' && str.charAt(i)<='z'){
                small++;
            }
            if (str.charAt(i) >= 'A' && str.charAt(i) <= 'Z'){
                big++;
            }
        }
        if (big==0 && small==0){
            return 0;
        }else if(big>0 && small>0){
            return 10;
        }else if(small>0 || big>0){
            return 20;
        }

        return 0;
    }

    public static int getNum(String str){
        int sum = 0;
        for(int i = 0;i<str.length();i++){
            if (str.charAt(i)-'0'>=0 && str.charAt(i)-'0'<=9){
                sum++;
            }
        }
        if (sum>1){
            return 20;
        }else if(sum == 1){
            return 10;
        }else{
            return 0;
        }

    }

    public static int getSym(String str){
        int sum = 0;
        for(int i = 0;i<str.length();i++){
            if (!(str.charAt(i)>='A' && str.charAt(i)<='Z') &&
                    !(str.charAt(i)>='a' && str.charAt(i)<='z') &&
                    !(str.charAt(i)-'0'>=0 && str.charAt(i)-'0'<=9)){
                sum++;
            }
        }
        if (sum>1){
            return 25;
        }else if(sum == 1){
            return 10;
        }else{
            return 0;
        }


    }
*/











/*    public boolean checkWon(int[][] board) {
        int N = board.length;
        int sum = 0;
        int i = 0;
        int j = 0;
        for(i=0; i<N;i++){
            sum=0;
            for(j=0;j<N;j++){
                //求每一行元素的和,行号不变，变得是列号
                sum+=board[i][j];
            }
            if(sum==N){
                return true;
            }
        }

        for(i=0; i<N;i++){
            sum=0;
            for(j=0;j<N;j++){
                //求每一列元素的和,行号不变，变得是列号
                sum+=board[j][i];
            }
            if(sum==N){
                return true;
            }
        }

        sum = 0;
        for(i=0;i<N;i++){
            sum+=board[i][i];
        }
        if (sum==N){
            return true;
        }
        sum = 0;
        for(i=0;i<N;i++){
            sum+=board[i][N-1-i];
        }
        if (sum==N){
            return true;
        }
        return false;

    }*/




   /* public static void main(String[] args) {
        int a = addAB(100,20);
        System.out.println(a);
    }
    public static int addAB(int A, int B) {
        while (B!=0){
            int add = A^B;
            int cur = (A&B)<<1;
            A = add;
            B = cur;
        }
        return A;
    }

*/






/*    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] nums = new int[n+1][m+1];
        nums[0][0]=1;
        for(int i = 0;i<=n;i++){
            for(int j=0;j<=m;j++){
                if (i==0){
                    nums[i][j] = 1;
                }else if(j==0){
                    nums[i][j] = 1;
                }else{
                    nums[i][j] = nums[i-1][j]+nums[i][j-1];
                }
            }
        }
        System.out.println(nums[n][m]);




    }*/


}
